package algorithms.question.class12;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/permutation-in-string/
 * <p>
 * 给定长度为m的字符串aim，以及一个长度为n的字符串str
 * 问能否在str中找到一个长度为m的连续子串，
 * 使得这个子串刚好由aim的m个字符组成，顺序无所谓，
 * 返回任意满足条件的一个子串的起始位置，未找到返回-1
 *
 * @author guichang
 * @date 2021/8/8
 */

@SuppressWarnings("all")
public class Code1_满足aim子串的位置 {
    // 窗口 + 词频

    public static void main(String[] args) {
        String str = "abcdbfrc;";
        String aim = "fcr";
        MyUtil.print(indexOfAim(str, aim));
    }

    public static int indexOfAim(String str, String aim) {
        if (str == null || aim == null || str.length() == 0 || aim.length() == 0) {
            return -1;
        }
        if (str.length() < aim.length()) {
            return -1;
        }
        // 初始化词频表
        int[] wf = new int[256];
        for (char c : aim.toCharArray()) {
            wf[c]++;
        }
        char[] strs = str.toCharArray();
        int l = 0, r = 0, all = aim.length();
        // 初始化窗口
        for (; r < aim.length(); r++) {
            // 当前字符个数大于0，all才减一
            if (wf[strs[r]]-- > 0) {
                all--;
            }
        }
        // 窗口已形成，窗口开始移动
        while (r < strs.length) {
            // 判断之前的窗口是否符合
            if (all == 0) {
                return l;
            }
            // r+1之后判断
            if (wf[strs[r++]]-- > 0) {
                all--;
            }
            // l+1之前判断
            if (wf[strs[l++]]++ >= 0) {
                all++;
            }
        }
        // 最后一次要判断下
        return all == 0 ? l : -1;
    }

}